#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct BiTNode {
	ElemType data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode,* BiTree;

typedef struct tag_t {
	BiTree p;
	struct tag_t* pnext;
}tag_t,* ptag_t;

void PreOrder(BiTree T) {
	if (T != NULL) {
		putchar(T->data);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

int main() {
	char c;
	BiTree tree = NULL;
	BiTree pnew = NULL;
	ptag_t phead = NULL, ptail = NULL, listnew = NULL;
	while (scanf("%c",&c) != EOF) {
		if (c == '\n') {
			break;
		}
		pnew = (BiTree)calloc(1,sizeof(BiTNode));
		pnew->data = c;
		listnew = (ptag_t)calloc(1,sizeof(tag_t));
		listnew->p = pnew;
		if (NULL == tree) {
			tree = pnew;
			phead = listnew;
			ptail = listnew;
			continue;
		}
		else {
			ptail->pnext = listnew;
			ptail = listnew;
		}

		if (NULL == phead->p->lchild) {
			phead->p->lchild = pnew;
		}
		else if (NULL == phead->p->rchild) {
			phead->p->rchild = pnew;
			phead = phead->pnext;
		}
	}
	PreOrder(tree);
	return 0;
}
